МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
1.Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=5Б , n2=3П, n3=2І – КІ-44
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Артим Віталій Ігорович КІ-44:
декодування вибраних літер для n1,n2,n3 відбувається на основі таблиці:
n1
n2
n3
А-120
Б-110
В-100
Г-90
Ґ-80
Д-70
Е-60
А-64
Б-72
В-56
Г-88
Ґ-96
Д-104
Е-112
А-117
Б-95
В-73
Г-195
Ґ-301
Д-247
Е-149
Є-140
Ж-130
З-150
И-160
І-170
Ї-180
Й-190
Є-128
Ж-146
З-154
И-168
І-176
Ї-184
Й-192
Є-93
Ж-111
З-127
И-349
І-181
Ї-163
Й-217
К-200
Л-210
М-220
Н-230
О-240
П-250
Р-260
К-208
Л-216
М-224
Н-232
О-248
П-256
Р-264
К-307
Л-325
М-251
Н-67
О-333
П-241
Р-159
С-270
Т-280
У-50
Ф-40
Х-290
Ц-300
Ч-310
С-272
Т-288
У-296
Ф-304
Х-312
Ц-328
Ч-336
С-234
Т-91
У-181
Ф-143
Х-37
Ц-45
Ч-129
Ш-320
Щ-330
Ь-340
Ю-350
Я-360
Ш-344
Щ-352
Ь-48
Ю-368
Я-376
Ш-225
Щ-71
Ь-167
Ю-349
Я-118
Згідно з таблицею отримаємо такі значення n1,n2,n3:
n1=5Б – О = 240 n2=3П – Т = 288 n3=2І – I = 181
Отже маємо матрицю А(240*288) та матрицю В(288*181)
2. Розробити та описати алгоритм множення матриць А*В на структурі, яка задається виразом:
3b-6b-2b-5b-10b-13b-14b-11b – КІ-44, де «nb»- номер букви П.І.Б студента.
Артим Віталій Ігорович КІ-44:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
А
Р
Т
И
М
В
І
Т
А
Л
І
Й
І
Г
О
Р
О
В
И
Ч
3
1
4
2
5
8
6
7
Отримаємо – ТВРМЛІГЙ
Для ТВРМЛІГЙ отримаємо 198,203,93,43,212,223,74,146. Даний набір чисел записуємо у стовпець і переводимо в двійкове 8-ми розрядне число. В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0:
192 – 11000110
203 - 11001011
093 - 01011101
043 - 00101011
212 - 11010100
223 - 11011111
074 - 01001010
146 – 10010010
=>
01000110
10001011
01011101
00101011
11010100
11011011
01001000
10010010
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами.
3.Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
КІ-41 … КІ-46: type=1(спільна пам’ять),type=2(через один процесор), type=3(розподілена пам’ять).
0909622
type=(0+9+0+9+6+2+2)=28 mod 3 + 1 = 2 (через один процесор)
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k - кількість цифр в номері залікової книжки.
tU=10tS=7tP=3tZ=3tW
Розміри матриць
Кількість процесорів (Р)
Тип початкового завантаження даних
Співвідношення часових параметрів
n1
n2
n3
240
288
181
8
через один з процесорів
Tu=10Ts=7Tp=3Tz=3Tw
Анотація
В даній курсовій роботі було розроблено програму для множення двох матриць розміром 240*288 та 288*181 на восьми процесорах, з заданою структурою зв’язків. Завантаження даних в процесори відбувається через один із них. Збір даних відбувається у тому ж процесорі з якого відбувалося завантаження. Також було визначено основні характеристики розроб...
